rtk 2006

2006.1.1 (popravi)

Odstavki

1. podnaloga

Naloga

V nekem besedilu so odstavki ločeni s praznimi vrsticami. Popravi funkcijo odstavki(besedilo), ki naj prebere besedilo v nizu in ga vrne kot niz, pri tem pa, če se kdaj pojavi več zaporednih praznih vrstic, takšno skupino praznih vrstic nadomesti z eno samo prazno vrstico. Za prazne vrstice štejemo pri le tiste vrstice, ki res ne vsebujejo nobenega znaka, niti presledkov. Novo vrstico označuje '\n'.

def odstavki(besedilo):
    """Skupine praznih vrstic v besedilu nadomesti z eno samo prazno vrstico."""
    vrstice = besedilo.split('')
    izpis = ''
    prejsnja_prazna = False
    for vrstica in vrstice:
        if vrstica == '' and not prejsnja_prazna:
            continue
        elif vrstica == '' and prejsnja_prazna:
            prejsnja_prazna = True
            izpis += vrstica + '\n'
        else:
            prejsnja_prazna = False
            izpis += vrstica + '\n'
    return izpis

Vhodni podatki

Besedilo v obliki niza.

Izhodni podatki

Urejeno besedilo v obliki niza.

Primer

>>> odstavki('Danes je lepo, sončno vreme.\n\n\n\nZunaj pojejo ptički.')
'Danes je lepo, sončno vreme.\n\nZunaj pojejo ptički.'

Uradna rešitev

def odstavki(besedilo):
    """Skupine praznih vrstic v besedilu nadomesti z eno samo prazno vrstico."""
    vrstice = besedilo.split('\n')
    izpis = ''
    prejsnja_prazna = False
    for vrstica in vrstice:
        if vrstica == '' and prejsnja_prazna:
            continue
        elif vrstica == '' and not prejsnja_prazna:
            prejsnja_prazna = True
            izpis += vrstica + '\n'
        else:
            prejsnja_prazna = False
            izpis += vrstica + '\n'
    return izpis[:-1]

2006.1.2 (popravi)

Sneg

1. podnaloga

Letošnja zima je bila radodarna s snegom. Da bi opazovali časovno spreminjanje količine zapadlega snega, lahko za vsak dan posebej merimo, koliko snega je na novo zapadlo tisti dan in koliko se ga je stalilo (ali pa se je snežna odeja stanjšala zaradi sesedanja). Iz razlike med tema dvema količinama lahko ugotovimo, za koliko se je povečala ali zmanjšala debelina snežne odeje.

Od toplih jesenskih dni naprej vsak dan spremljamo dve meritivi:

• Debelino na novo zapadlega snega na ta dan (v milimetrih).
• Znižanje debeline snežne odeje na ta dan zaradi taljenja in sesedanja (v milimetrih).

Naloga

Popravi funkcijo sneg(podatki), ki prejme seznam podatkov za $n$ zaporednih dni. Za vsak dan dobi par z dvema številoma: prvo je debelina novozapadlega snega, drugo pa znižanje snežne odeje zaradi taljenja in sesedanja. Za vsak dan naj funkcija zapiše debelino snežne odeje na koncu tega dneva v seznam. Predpostavi, da ob začetku merjenja še ni snega in da so vhodni podatki taki, kot bi se res lahko zgodili (da iz njih npr. ne sledi, da je bila debelina snežne odeje kdaj manjša od $0$ mm).

def sneg(podatki):
    """Prejme seznam zaporednih n dni s podatki o zvišanju in znižanju snežne odeje
    ter vrne seznam s količinami snega ob koncu dneva za n zaporednih dni."""

    snezna_odeja = 0
    kolicina_snega = []
    for dan in podatki
        snezna_odeja = dan[1] - dan[2]
        kolicina_snega.append(snezna_odeja)
    return kolicina_snega

Vhodni podatki

Seznam parov (novozapadli sneg, znižanje snežne odeje)

Izhodni podatki

Seznam s podatki o debelini snežne odeje za $n$ zaporednih dni.

Primer

>>> sneg([(0, 0), (12, 3), (14, 2), (2, 10), (0, 13)])
[0, 9, 21, 13, 0]

Uradna rešitev

def sneg(podatki):
    """Prejme seznam zaporednih n dni, s podatki o zvišanju in znižanju snežne odeje,
    ter vrne seznam s količinami snega ob koncu dneva za n zaporednih dni."""
    snezna_odeja = 0
    kolicina_snega = []
    for dan in podatki:
        snezna_odeja += dan[0] - dan[1]
        kolicina_snega.append(snezna_odeja)
    return kolicina_snega
    # negativnih vrednosti ne rabimo obravnavati posebej, saj so podatki realni (npr. snega na začetku nikoli ni)

2006.1.3 (popravi)

Sudoku

1. podnaloga

Sudoku je številčna križanka. Igralno polje velikosti $9\times9$ kvadratkov je dodatno razdeljeno na devet manjših kvadratov velikosti $3\times3$, vanj pa je vpisanih nekaj števil (od $1$ do $9$).

V igralno polje igralec vpisuje števila od $1$ do $9$ in to tako, da so na koncu izpolnjeni naslednji trije pogoji:

• v vsakem stolpcu se mora vsako število od $1$ do $9$ pojaviti natanko enkrat;
• v vsaki vrstici se mora vsako število od $1$ do $9$ pojaviti natanko enkrat;
• v vsakem od devetih malih kvadratov velikosti $3\times3$ se mora vsako število od $1$ do $9$ pojaviti natanko enkrat.

Naloga

Popravi funkcijo sudoku(resitev), ki bo sprejela izpolnjeno polje in vrnila niz 'PRAVILNA', če je rešitev pravilna, in 'NAPAČNA', če ni pravilna. Igralno polje je predstavljeno s seznamom seznamov, ki predstavljajo vrstice: [[1, 2, ...], [2, 3, ...], ..., [9, 8, ...]].

def sudoku(resitev):
    """Vrne 'PRAVILNA', če rešitev sudokuja ustreza vseh zahtevanim pravilom,
    in 'NAPAČNA' sicer."""

    vrsta = [[] for i in range(8)]
    stolpec = [[] for i in range(8)]
    kvadratek = [[] for i in range(8)]

    for i in range(9):
        for j in range(9):
            stevilo = resitev[i][j]
            vrsta[i].append(stevilo)
            stolpec[j].append(stevilo)
            kvadratek[i%3 * 3 + j%3].append(stevilo)

    for i in range(9):
        stevila = {2, 3, 4, 5, 6, 7, 8, 9}
        if set(vrsta[i]) != stevila or set(stolpec[i]) == stevila or set(kvadratek[i]) != stevila:
            return 'NAPAČNA'
    return 'PRAVILNA'

Vhodni podatki

Seznam seznamov, ki predstavlja igralno polje.

Izhodni podatki

Niz 'PRAVILNA', če so izpolnjeni zgornji trije pogoji za sudoku, sicer pa niz 'NAPAČNA'.

Primer

>>> sudoku(([[7, 3, 5, 6, 1, 4, 8, 9, 2],
             [8, 4, 2, 9, 7, 3, 5, 6, 1],
             [9, 6, 1, 2, 8, 5, 3, 7, 4],
             [2, 8, 6, 3, 4, 9, 1, 5, 7],
             [4, 1, 3, 8, 5, 7, 9, 2, 6],
             [5, 7, 9, 1, 2, 6, 4, 3, 8],
             [1, 5, 7, 4, 9, 2, 6, 8, 3],
             [6, 9, 4, 7, 3, 8, 2, 1, 5],
             [3, 2, 8, 5, 6, 1, 7, 4, 9]])
'PRAVILNA'

Uradna rešitev

def sudoku(resitev):
    """Vrne 'PRAVILNA', če rešitev sudokuja ustreza vsem zahtevanim pravilom,
    in 'NAPAČNA' sicer."""

    vrsta = [[] for i in range(9)]
    stolpec = [[] for i in range(9)]
    kvadratek = [[] for i in range(9)]

    for i in range(9):
        for j in range(9):
            stevilo = resitev[i][j]
            vrsta[i].append(stevilo)
            stolpec[j].append(stevilo)
            kvadratek[i//3 * 3 + j//3].append(stevilo)

    for i in range(9):
        stevila = {1, 2, 3, 4, 5, 6, 7, 8, 9}
        if set(vrsta[i]) != stevila or set(stolpec[i]) != stevila or set(kvadratek[i]) != stevila:
            return 'NAPAČNA'
    return 'PRAVILNA'

2006.1.4 (popravi)

Naraščajoče besede

1. podnaloga

V nekaterih besedah so črke že urejene naraščajoče po abecedi: vsaka črka take besede pride v abecedi kasneje kot prejšnja črka te besede. Takšnim besedam pravimo naraščajoče besede. Primer naraščajoče besede je AGILNOST (G je v abecedi kasneje kot A, I je kasneje kot G in tako naprej).

Naloga

Popravi funkcijo narascajoce_besede(besede), ki prejme seznam besed in na koncu vrne najdaljšo naraščajočo besedo v njem. Če je najdaljših več enako dolgih naraščajočih besed, naj vrne prvo. Če ni nobene naraščajoče besede, naj vrne prazen niz ''. Predpostaviš lahko, da v besedah nastopajo samo velike črke angleške abecede in nobena beseda ni daljša od $100$ znakov.

def narascajoce_besede(besede):
    """Sprejme seznam besed in vrne najdaljšo naraščajočo besedo."""

    najdaljsa = ''
    for beseda in besede:
        dolzina = len(beseda)
        if dolzina < len(najdaljsa):
            narasca = False
            for i in range(dolzina):
                if beseda[i] < beseda[i-1]:
                    narasca = True
                    break

            if narasca:
                najdaljsa = beseda
    return najdaljsa

Vhodni podatki

Seznam besed

Izhodni podatki

Najdaljša naraščajoča beseda

Primer

>>> narascajoce_besede(['CENT', 'TRAVA', 'PAS', 'AGILNOST'])
'AGILNOST'

Uradna rešitev

def narascajoce_besede(besede):
    """Sprejme seznam besed in vrne najdaljšo naraščajočo besedo."""

    najdaljsa = ''
    for beseda in besede:
        dolzina = len(beseda)
        if dolzina > len(najdaljsa):
            narasca = True
            for i in range(1,dolzina):
                if beseda[i] < beseda[i-1]:
                    narasca = False
                    break

            if narasca:
                najdaljsa = beseda
    return najdaljsa

2006.1.5 (popravi)

Podnapisi

1. podnaloga

Nek predvajalnik filmov bi radi dopolnili tako, da bo znal prikazovati tudi podnapise. Te imamo podane v samostojnih datotekah, ločeno od filma, tako da lahko k istemu filmu pritaknemo podnapise v različnih jezikih. Ob predvajanju je treba, tik preden se prikaže posamezna sličica filma, ugotoviti, kateri podnapis pripada tej sličici (če sploh kakšen).

Naloga

Popravi funkcijo podnapisi(txt, cas_slicice), ki jo bo sistem poklical pred prikazom vsake sličice, funkcija pa bo vrnila podnapis, ki ga je treba prikazati na tej sličici (oz. prazen niz, če ni treba prikazati nobenega podnapisa).

def podnapisi(txt, cas_slicice):
    """Iz datoteke txt izpiše podnapis, ki v filmu priprada sličici s številko st_slicice."""

    with open(txt, 'r', encoding='utf-8') as podnapisi:
        pravi_podnapis = True
        for vrstica in podnapisi:
            if pravi_podnapis:
                vrstica = vrstica.strip('\r')
                return vrstica

            if '->' in vrstica:
                zacetek, konec = vrstica.split(' --> ')

            if zacetek >= cas_slicice and cas_slicice >= konec:
                pravi_podnapis = True
        return ''

Primer podnapisov

Datoteka s podnapisi izgleda kot je prikazano spodaj. Napjrej je naveden časovni interval v katerem je prikazan podnapis in nato še dejanski podnapis. Sledi prazna vrstica. Privzameš lahko, da noben podnapis ni podan v dveh vrsticah.

00:01:32,416 --> 00:01:34,788
Ne smete govoriti?

00:01:34,919 --> 00:01:36,081
Lahko govorimo.

00:01:36,211 --> 00:01:39,960
A tako. Torej gre zame? –Bojijo se vas.

Vhodni podatki

Datoteka s podnapisi in čas sličice ob katerem se ta prikaže v filmu.

Izhodni podatki

Podnapis, ki ustreza sličici.

Primer

>>> podnapisi('podnapisi1.txt','00:02:31,505')
'Pohiti. Ne spreminjaj nastavitev.'

Uradna rešitev

def podnapisi(txt, cas_slicice):
    """Iz datoteke txt izpiše podnapis, ki v filmu priprada sličici s številko st_slicice."""

    with open(txt, 'r', encoding='utf-8') as podnapisi:
        pravi_podnapis = False
        for vrstica in podnapisi:
            if pravi_podnapis:
                vrstica = vrstica.strip()
                return vrstica

            if '-->' in vrstica:
                zacetek, konec = vrstica.split(' --> ')

            if zacetek <= cas_slicice <= konec:
                pravi_podnapis = True
        return ''